/// @tags: Fibonacci NumberTheory
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef unsigned int uint;
typedef long long LL;

int const N = 1e4, S = 3e7 + 5;
int const Pi[] = {0, 0, 3, 8, 0, 20};

char s[S];
uint p;
LL pri[N], k[N];

struct Matrix {
  uint a[2][2];

  Matrix() { memset(a, 0, sizeof(a)); }

  inline Matrix operator*(Matrix const &rhs) const {
    Matrix res;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j)
        for (int k = 0; k < 2; ++k)
          if ((res.a[i][j] += (LL)a[i][k] * rhs.a[k][j] % p) >= p) res.a[i][j] -= p;
    return res;
  }

  inline Matrix operator^(LL k) const {
    Matrix base(*this), res;
    res.a[0][0] = res.a[1][1] = 1;
    for (; k; k >>= 1, base = base * base)
      if (k & 1) res = res * base;
    return res;
  }
} A;

LL getGCD(LL a, LL b) { return b ? getGCD(b, a % b) : a; }

inline LL getLCM(LL n, LL m) { return n / getGCD(n, m) * m; }

inline uint getFib(LL n) {
  Matrix a, ans;
  a.a[0][0] = a.a[0][1] = a.a[1][0] = 1, a.a[1][1] = 0;
  ans = a ^ n;
  return ans.a[0][1];
}

inline LL solve(LL x) {
  int cnt = 0;
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) {
      pri[++cnt] = i, k[cnt] = 1;
      while (x % i == 0) x /= i, k[cnt] *= i;
    }
  for (int i = 1; i <= cnt; ++i) k[i] /= pri[i];
  if (x != 1) k[++cnt] = 1, pri[cnt] = x;
  for (int i = 1; i <= cnt; ++i)
    if (pri[i] <= 5) k[i] *= Pi[pri[i]];
    else if (pri[i] % 5 == 1 || pri[i] % 5 == 4)
      k[i] *= pri[i] - 1;
    else
      k[i] *= (pri[i] + 1) << 1;
  LL res = k[1];
  for (int i = 2; i <= cnt; ++i) res = getLCM(res, k[i]);
  return res;
}

inline int main() {
  cin >> s >> p;
  int len = strlen(s);
  if (p == 1) return cout << 0, 0;
  LL m = solve(p), n = 0;
  for (int i = 0; i < len; ++i) n = (n * 10 + (s[i] ^ 48)) % m;
  if (!n) return cout << 0, 0;
  if (n == 1) return cout << 1, 0;
  return cout << getFib(n), 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4000 斐波那契数列.in", "r", stdin);
  freopen("P4000 斐波那契数列.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
